#!/usr/bin/env python

import sys
import re
import itertools
from itertools import izip_longest
from itertools import imap
from collections import Counter
import argparse
import time

def parse_range(astr):
    result = set()
    for part in astr.split(','):
        x = part.split('-')
        result.update(range(int(x[0]), int(x[-1]) + 1))
    return sorted(result)

def sortby(x):
   # return x.split()[0]
   # largest, address, order
   return int(x.split()[2]), x.split()[0], int(x.split()[3])

def sortby1(x):
   # return x.split()[0]
   # largest, address, order
   return int(x.split()[1]), x.split()[0]


def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

cyclesdata = []
cyclesresultstrings = []
cyclesuses = []


def buildcyclerangesets(start, stop):

   global cyclesdata
   global cyclesresultstrings
   global cyclesuses

   cyclerangesets = []

   for i in range(start, stop):

      cycle = cyclesdata[i]
      sys.stderr.write('build range for cycle %d\n' %(i + 1))
      cycle = list(set(cycle))
      cycle.sort()
      cyclerange = []
      for item in cycle:
         l = list(item)
         cyclerange.extend(range(l[0], l[0] + l[2]))

      #sys.stderr.write('(%d Bytes)\n' % sys.getsizeof(cyclerange));

      cyclerangesets.append(set(cyclerange))

      cyclerange = []

   return cyclerangesets


def main():

   global cyclesdata

   cycledata = []

   if len(sys.argv) >= 5:

      cyclesrange = parse_range(sys.argv[4])

      cyclenr = 0
      allow = False

      order = 1

      f = open(sys.argv[1])

      sys.stderr.write('collecting data for cycles ')

      for line in f:

         if line.startswith('DSC'):
            if re.search(sys.argv[2], line):

               if cycledata:

                  addrs = []
                  largests = []
                  for cd in cycledata:
                     cdl = list(cd)
                     a = cdl[0]
                     s = cdl[2]
                     if a not in addrs:
                        addrs.append(a)
                        largests.append(s)
                     else:
                        if s > largests[addrs.index(a)]:
                           largests[addrs.index(a)] = s

                  #for p in addrs:
                  #   print hex(p), largests[addrs.index(p)]

                  i = 0;
                  for c in cycledata:
                     b = largests[addrs.index(list(c)[0])]
                     cycledata[i] = cycledata[i] + (b,)
                     i+= 1


                  cyclesdata.append(cycledata)

                  cyclesresultstrings.append([''] * len(cycledata))
                  cyclesuses.append([0] * len(cycledata))

                  #sys.stderr.write('%s\n' % str(cyclesresultstrings))
                  #sys.stderr.write('%s\n' % str(cyclesuses))


               cycledata = []
               cyclenr += 1

               order = 1

               allow = True

               if cyclenr in cyclesrange:
                  sys.stderr.write('+')
                  sys.stderr.flush()
               else:
                  if cyclenr > max(cyclesrange):
                     break
                  else:
                     sys.stderr.write('-')
                     sys.stderr.flush()


            elif re.search(sys.argv[3], line):

               allow = False


         if allow:

            if cyclenr in cyclesrange:

               if line.startswith('DSC'):

                  result = re.search(r'(r|m),=[0-9a-f]+,ra=[0-9a-f]+,sz=[0-9]+', line)
                  #result = re.search(r'r,=[0-9a-f]+,ra=[0-9a-f]+,sz=[0-9]+', line)
                  #result = re.search(r'm,=[0-9a-f]+,ra=[0-9a-f]+,sz=[0-9]+', line)

                  if result:

                     malloc = int((result.group().split(',')[1])[1:], 16)
                     #address = int((result.group().split(',')[2])[3:], 16)
                     size = int((result.group().split(',')[3])[3:])
                     tag = line.split(' ')[3][:-1].split(',=')[0]

                     if malloc < 0x30000000:

                        cycledata.append((malloc, tag, size, order))
                        order+= 1

      sys.stderr.write('\n')

      f.close()




      """
      for row in izip_longest(*cyclesdata):
         print row
      """

      """
      sys.stderr.write('here1\n')
      cyclesdata_union = sorted(set().union(*cyclesdata))
      sys.stderr.write('here2\n')
      new_lists = [[x if x in my_list else "----------" for x in cyclesdata_union] for my_list in cyclesdata]
      sys.stderr.write('here3\n')

      for row in izip_longest(*new_lists):
         for item in row:
            print str(item).replace(',',''),
            print ',',
         print
      """

      leakchecklists = []

      if len(sys.argv) >= 6:
         nrcyclestocheck = int(sys.argv[5])
      else:
         nrcyclestocheck = max(cyclesrange) - min(cyclesrange) + 1

      for cycletocheckfrom in range(0, nrcyclestocheck):

         nrfuturecycleschecked = 0

         sys.stderr.write('checking cycle %d\n' % (cycletocheckfrom + 1))

         cycle = list(set(cyclesdata[cycletocheckfrom]))
         cycle.sort()


         cycleresultstrings = cyclesresultstrings[cycletocheckfrom]
         cycleuses = cyclesuses[cycletocheckfrom]



         leakchecklist_full = []
         leakchecklist_leaksonly = []
         leakchecklist_leaksonly_minimized = []


         #break into groups of 4 cycles, rebuild cyclesets to prevent oom,
         #we cannot hold many cyclesets into memory before running at 99%
         #and slowing down to a crawl
         start = cycletocheckfrom
         stop = max(cyclesrange) - min(cyclesrange) + 1
         length = stop - start

         for group in range(0, length / 4 + 1):

            count = 4
            if length - (group * 4) < 4:
               count = length - group * 4

            cyclesets = buildcyclerangesets(start + group * 4, start + group * 4 + count)

            sys.stderr.write('checking against future cycle(s) : ')
            for c in range(start + group * 4, start + group * 4 + count):
               sys.stderr.write(' %d' % int(c + 1))
            sys.stderr.write('\n')


            # check cycle against futurecycles
            i = 0
            for item in cycle:
               itemlist = list(item)
              

               if not cycleresultstrings[i]:
                  cycleresultstrings[i] = str('0x%08x %6d %6d %6d %-60s') %(itemlist[0], itemlist[2], itemlist[4], itemlist[3], itemlist[1])

               rs = set(range(itemlist[0], itemlist[0] + itemlist[2]))
               for cycleset in cyclesets:

                  if bool(rs & cycleset):
                     cycleresultstrings[i] += '+'
                     cycleuses[i] += 1
                  else:
                     cycleresultstrings[i] += '-'

               i+= 1

            nrfuturecycleschecked+= count

            if len(sys.argv) == 7:
               if nrfuturecycleschecked >= int(sys.argv[6]):
                  sys.stderr.write('stop due to nrfuturecycleschecked = %d >= %s\n' %(nrfuturecycleschecked, sys.argv[6]))
                  break

         k = 0
         for t in cycleresultstrings:
            if cycleuses[k] == 1:
               cycleresultstrings[k]+= '!'
               leakchecklist_leaksonly.append(cycleresultstrings[k])
               #sys.stderr.write('%s\n' % tempstrings[k])
            k+= 1



         leakchecklist_leaksonly.sort(key = sortby, reverse=True)
         #sys.stderr.write('sorted -----------------------------------------------------------\n')
         #for r in leakchecklist_leaksonly:
         #   sys.stderr.write('%s\n' % str(r))


         addrs = []
         total = 0

         for r in leakchecklist_leaksonly:
            if not r.split()[0] in addrs:
               leakchecklist_leaksonly_minimized.append(str('%s %s' %(r.split()[4], r.split()[1])))
               addrs.append(r.split()[0])
               total += int(r.split()[1])

         leakchecklist_leaksonly_minimized.sort(key = sortby1, reverse=True)

         #sys.stderr.write('minimized -----------------------------------------------------------\n')

         for r in leakchecklist_leaksonly_minimized:
            sys.stderr.write('%s\n' % str(r))
         sys.stderr.write('total = %d Bytes\n' % total)

         leakchecklist_leaksonly_minimized.insert(0, 'total = %d Bytes' %total)
         leakchecklist_leaksonly_minimized.append('total = %d Bytes' %total)


         leakchecklists.append(leakchecklist_leaksonly_minimized)


      for row in izip_longest(*leakchecklists):
         print row


   else:
      sys.stderr.write("Usage: %s tdifile cyclepattern-start cyclepattern-end cyclerange [nrcyclestocheck] [maxnrfuturecyclestocheckagainst]\n" % sys.argv[0])

if __name__ == "__main__":
   main()
